In electronic graphic systems the painting or drawing of an image can be simulated by electronic means. Several different processing techniques by which data representing a painted image is written into a memory are now well established. In most techniques the user is provided with a choice of notional painting or drawing implements, such as a paintbrush, a pencil or an airbrush for example, and manipulation by the user of an input device such as a stylus and touch tablet results in the painting of an image. The painted image is usually displayed on a monitor with new strokes and lines being added to the display substantially in real time. In this way the effect of manipulating the stylus is seen apparently instantaneously thereby adding realism to the painting performed by the user.
An early technique sometimes used for painting an image into a memory is the so-called Z-paint algorithm. A painting implement, hereinafter called "brush", is defined by data values Z for a patch of pixels. The Z-values may denote different colours on a colour map or different intensities on a grey scale. Further Z values are associated with the various pixels of the image memory, representing either an initial background image or values resulting from previous paintings. As painting progresses, for each instantaneous position of the brush the Z values of the brush pixels are compared with the Z values of corresponding image pixels and the brush pixels replace the image pixels in the image store if the brush Z values are the greater than those of the image pixels, but leave the image pixel Z values unchanged otherwise. A "yes-no" choice is made for each image pixel inserted by the brush and therefore Z-paint can be described as a binary algorithm.
This technique enables the user to paint lines having pixels of varying colours or varying shades of grey. However, this approach has the disadvantage that the lines which are painted exhibit jagged edges due to the sampling which is inherent in the technique and some methods of reducing this disadvantage are described in an article by Turner Whitted in Computer Graphics, Volume 17, Number 3, July 1983, entitled Anti-aliased line drawing using brush "extrusion".
One of these methods is to paint on a neutral background initially composed of pixels of a uniform and minimum Z value (black) with a filtered high resolution brush. The pixels of the brush have Z values which decrease from the centre of the brush toward the edge, and as the brush is moved along a high resolution path the final intensity of grey painted by the brush decreases with perpendicular distance from the path. As described in the article, the fact that the brush is positioned with a higher resolution than that of the pixels of the background image, together with the grey "shading", will make jagged edges less noticeable. Nevertheless the method has the disadvantage that lines have to be drawn as isolated images and later incorporated with the desired background image, which would presumably be different from the neutral background on which the lines are drawn, as a separate step. Consequently the user cannot observe the effect of painting in real time.
The use of an "extrusion" brush is also proposed in the article to reduce the problem of jagged edges while at the same time enabling the user to observe the effect of painting in real time. In this brush extrusion technique the filtered high resolution brush is represented by a set of values ascribed to a single line of pixels perpendicular to the direction of motion of the brush. The brush values in this case are not Z values but interpolating coefficients to control merging of user selected brush colours with the colour of the background image at corresponding background pixels identified by the positioning of the brush. The coefficients have maximum values for pixels at or near the longitudinal axis of the line being drawn and decline in value with increasing distance from the axis. The coefficients for the line of pixels have to be generated anew for each brush position along a stroke and this is done by summing precalculated values derived from a circularly symmetrical brush along lines parallel to the direction of brush movement, at each brush position.
The brush extrusion technique described in the preceding paragraph generates a representation of the distribution of interpolating coefficients required to interpolate a line of the selected colour into the background image. The representation has of course to be generated in advance of the interpolation. Advantage is taken of the fact that the line is generated in successive small segments corresponding to the transverse line of pixels by which the brush is represented. A cache store is provided in which the coefficients for each segment are written as they are generated. When the brush is moved to it's next position, the coefficients for the previous segment are read from the cache store and fed to an interpolator where the user selected colour is merged, pixel by pixel within the segment, with colours read from the corresponding pixels in the image store. The resultant modified image pixel values are then written back to the image store. The image store is also serially read to a display monitor on which the user can observe instantly in real time, the effect of his painting. The use of interpolation under control of the brush coefficients has the advantage of reducing significantly the appearance of jagged edges.
If it is desired to use the Z-paint algorithm together with the extrusion brush technique, the brush pixels must be provided with Z values separate from the interpolation coefficients. The extrusion brush technique reduces the problem of jagged edges, but introduces another problem, namely that the extrusion brush tends to produce unacceptable effects at the beginning and end of a drawn line. It may also produce discontinuities between line segments, especially if the direction of movement of the brush changes along the length of the line.
Prior to the Turner Whitted paper we proposed our own system for reducing the problem of aliasing in an electronically created image. In our solution we define a brush or other drawing implement as a patch of pixels. The patch of pixels defines a continuous three-dimensional shape representing the distribution round the centre of the implement, which shape has a high central region and decreases in height to the edge of the shape. As the user manipulates an input device, such as a stylus and touch tablet, co-ordinate positions are generated representing the instantaneous position of the brush on an image as stored in a memory. For each co-ordinate position a patch of image pixels is read from the memory, modified by combining the pixels with corresponding pixels in the brush such that the resulting pixels are a weighted combination of the image pixels and the brush pixels, and then writing the resulting pixels back into the memory to replace the pixels previously there. This approach is disclosed in detail in our British Patent No. 2,089,625 and corresponding U.S. Pat. No. 4,514,818, the teachings of which are incorporated herein by reference. The systems disclosed in these patents are able to paint substantially non-aliased lines and therefore provide for realistic painting in an electronic environment.
In our British Patent No. GB 2,113,950 and corresponding U.S. Pat. No. 4,602,286, the teachings of which are incorporated herein by reference, we disclose a graphic system which enables a foreground image or a portion thereof to be merged into a background image. In this system, a control image is created for example by painting a one-dimensional or monochrome image into a framestore. The control image defines a mask or stencil with graduated edges and the user is free to experiment with the form of the stencil and with spatial transformations or movements of stencil and the foreground image on the background image by manipulation of a stylus and touch tablet for example. In a trial and error phase, the foreground and background images can be combined with the aid of the control image so that the user can observe the potential effect on a monitor. Once the user is satisfied with the effect, the foreground image is selectively committed to the background image using the control image as an interpolation coefficient on a pixel by pixel basis, the resultant combination replacing the initial background image.